from PySide6.QtWidgets import (
    QApplication,
    QMainWindow,
    QWidget,
    QPushButton,
    QVBoxLayout,
)
from PySide6.QtGui import QPainter, QPen, QColor, QBrush
from PySide6.QtCore import Qt, QPoint, QRect

CELL_SIZE = 30  # 格子像素尺寸

"""计算Bresenham路径"""

def bresenham_line(start, end):
    x0, y0 = start
    x1, y1 = end
    dx = abs(x1 - x0)
    dy = abs(y1 - y0)
    sx = 1 if x0 < x1 else -1
    sy = 1 if y0 < y1 else -1
    err = dx - dy
    path = []

    while True:
        path.append((x0, y0))
        if x0 == x1 and y0 == y1:
            break
        e2 = 2 * err
        if e2 > -dy:
            err -= dy
            x0 += sx
        if e2 < dx:
            err += dx
            y0 += sy
    return path

def bresenham_line2(start, end):
    """Bresenham直线算法实现
        https://blog.csdn.net/weixin_44483794/article/details/144565448
    参数：
        start: 起点坐标元组 (x0, y0)
        end: 终点坐标元组 (x1, y1)
    返回：
        路径点列表，包含所有经过的格子坐标
    """
    x0, y0 = start
    x1, y1 = end
    dx = abs(x1 - x0)
    dy = abs(y1 - y0)
    
    # 确定步进方向
    sx = 1 if x0 < x1 else -1
    sy = 1 if y0 < y1 else -1
    
    path = []

    x = x0
    y = y0

    err = 0

    while True:
        path.append((x,  y))

        if x == x1 and y == y1:
            break
        
        if dx > dy:
            # x轴长
            err += dy

            # if err > dx / 2:
            if 2 * err > dx:
                y += sy
                err -= dx
            
            x += sx
        else:
            # y轴长
            err += dx
            
            # if err > dy / 2:
            if err * 2 > dy:
                x += sx
                err -= dy
            
            y += sy
        
    return path

def super_coverLine2(start, end):
    x0, y0 = start
    x1, y1 = end
    dx = abs(x1 - x0)
    dy = abs(y1 - y0)
    
    # 确定步进方向
    sx = 1 if x0 < x1 else -1
    sy = 1 if y0 < y1 else -1
    
    path = []

    x = x0
    y = y0

    err = dy if dx > dy else dx
    errprev = err

    while True:
        path.append((x,  y))

        if x == x1 and y == y1:
            break
        
        if dx > dy:
            # x轴长

            # if err > dx / 2:
            if 2 * err > dx:
                y += sy
                err -= dx

                if err + errprev < dx:
                    # 底部
                    path.append((x + sx,  y - sy))
                elif err + errprev > dx:
                    # 左边
                    path.append((x, y))
                else:
                    # 底部和左边
                    path.append((x + sx,  y - sy))
                    path.append((x, y))
            
            err += dy
            x += sx
        else:
            # y轴长
            
            # if err > dy / 2:
            if 2 * err > dy:
                x += sx
                err -= dy
            
            if err + errprev < dy:
                path.append((x - sx,  y + sy))
            elif err + errprev > dy:
                path.append((x, y))
            else:
                path.append((x - sx,  y + sy))
                path.append((x, y))
            
            err += dx
            y += sy

        errprev = err
        
    return path

def super_coverLine(start, end):
    x1, y1 = start
    x2, y2 = end

    path = []

    ystep: int = 0
    xstep: int = 0  # the step on y and x axis
    error: int  # the error accumulated during the increment
    errorprev: int  # *vision the previous value of the error variable
    y = y1
    x = x1  # the line points
    ddy: int = 0
    ddx: int = 0  # compulsory variables: the double values of dy and dx
    dx = x2 - x1
    dy = y2 - y1

    path.append((x1, y1))  # first point

    # NB the last point can't be here, because of its previous point (which has to be verified)
    if dy < 0:
        ystep = -1
        dy = -dy
    else:
        ystep = 1
    if dx < 0:
        xstep = -1
        dx = -dx
    else:
        xstep = 1
    ddy = 2 * dy
    # work with double values for full precision
    ddx = 2 * dx
    if ddx >= ddy:  # first octant (0 <= slope <= 1)
        # compulsory initialization (even for errorprev, needed when dx==dy)
        error = dx  # start in the middle of the square
        errorprev = error
        for i in range(0, dx):  # do not use the first point (already done)
            x += xstep
            error += ddy
            if error > ddx:  # increment y if AFTER the middle ( > )
                y += ystep
                error -= ddx
                # three cases (octant == right->right-top for directions below):
                if error + errorprev < ddx:  # bottom square also
                    path.append((x, y - ystep))
                elif error + errorprev > ddx:  # left square also
                    path.append((x - xstep, y))
                else:  # corner: bottom and left squares also
                    path.append((x, y - ystep))
                    path.append((x - xstep, y))
            path.append((x, y))
            errorprev = error
    else:  # the same as above
        errorprev = error = dy
        for i in range(0, dy):
            y += ystep
            error += ddx
            if error > ddy:
                x += xstep
                error -= ddy
                if error + errorprev < ddy:
                    path.append((x - xstep, y))
                elif error + errorprev > ddy:
                    path.append((x, y - ystep))
                else:
                    path.append((x - xstep, y))
                    path.append((x, y - ystep))
            path.append((x, y))
            errorprev = error
    return path


class GridCanvas(QWidget):
    def __init__(self):
        super().__init__()
        self.start_point = None
        self.end_point = None
        self.path = []
        self.path2 = []
        self.path3 = []
        self.setMinimumSize(600, 400)

    def paintEvent(self, event):
        painter = QPainter(self)
        self.draw_grid(painter)
        self.highlight_path(painter)

    def draw_grid(self, painter):
        """绘制基础网格"""
        painter.setPen(QPen(Qt.gray, 1, Qt.DotLine))

        # 绘制垂直线
        for x in range(0, self.width(), CELL_SIZE):
            painter.drawLine(x, 0, x, self.height())

        # 绘制水平线
        for y in range(0, self.height(), CELL_SIZE):
            painter.drawLine(0, y, self.width(), y)

    def highlight_path(self, painter):
        """标红路径格子"""
        if not self.path:
            return

        painter.setBrush(QBrush(QColor(255, 0, 0, 100)))
        painter.setPen(QPen(Qt.red, 2))

        for x, y in self.path:
            rect = QRect(x * CELL_SIZE, y * CELL_SIZE, CELL_SIZE, CELL_SIZE)
            painter.drawRect(rect)

        painter.setBrush(QBrush(QColor(0, 255, 0, 100)))
        painter.setPen(QPen(Qt.green, 2))

        for x, y in self.path2:
            rect = QRect(x * CELL_SIZE, y * CELL_SIZE, CELL_SIZE, CELL_SIZE)
            painter.drawRect(rect)

        # painter.setBrush(QBrush(QColor(255, 0, 0, 100)))
        # painter.setPen(QPen(Qt.red, 2))

        # for x, y in self.path3:
        #     rect = QRect(x * CELL_SIZE, y * CELL_SIZE, CELL_SIZE, CELL_SIZE)
        #     painter.drawRect(rect)


class MainWindow(QMainWindow):
    def __init__(self):
        super().__init__()
        self.canvas = GridCanvas()
        self.btn_clear = QPushButton("清除")

        layout = QVBoxLayout()
        layout.addWidget(self.btn_clear)
        layout.addWidget(self.canvas)

        container = QWidget()
        container.setLayout(layout)
        self.setCentralWidget(container)

        # 事件绑定
        self.canvas.mousePressEvent = self.on_click
        self.btn_clear.clicked.connect(self.clear_canvas)

    def on_click(self, event):
        pos = event.position()
        grid_pos = (int(pos.x() // CELL_SIZE), int(pos.y() // CELL_SIZE))

        if not self.canvas.start_point:
            self.canvas.start_point = grid_pos
        else:
            self.canvas.end_point = grid_pos
            self.calculate_path()

        self.canvas.update()

    def calculate_path(self):
        self.canvas.path = super_coverLine(
            self.canvas.start_point, self.canvas.end_point
        )

        self.canvas.path2 = bresenham_line2(
            self.canvas.start_point, self.canvas.end_point
        )

        # if set(self.canvas.path) != set(self.canvas.path3):
        #     print("super_coverLine not equal")
        #     print(f"path={self.canvas.path}")
        #     print(f"path2={self.canvas.path3}")
        #     print("")

    def clear_canvas(self):
        self.canvas.start_point = None
        self.canvas.end_point = None
        self.canvas.path = []
        self.canvas.update()


if __name__ == "__main__":
    app = QApplication([])
    window = MainWindow()
    window.show()
    app.exec()
